package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.com/problems/check-if-two-expression-trees-are-equivalent/'>检查两颗二叉树表达式是否等价(Check If Two Expression Trees are Equivalent)</a>
 * <p>二叉表达式树是一种表达算术表达式的二叉树。二叉表达式树中的每一个节点都有零个或两个子节点。 叶节点（有 0 个子节点的节点）表示操作数，非叶节点（有 2 个子节点的节点）表示运算符。在本题中，我们只考虑 '+' 运算符（即加法）。</p>
 * <p>给定两棵二叉表达式树的根节点 root1 和 root2 。如果两棵二叉表达式树等价，返回 true ，否则返回 false 。</p>
 * <p>当两棵二叉搜索树中的变量取任意值，分别求得的值都相等时，我们称这两棵二叉表达式树是等价的。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1:
 *      输入： root1 = [x], root2 = [x]
 *      输出： true
 *
 * 示例 2:
 *      输入：root1 = [+,a,+,null,null,b,c], root2 = [+,+,a,b,c]
 *                  +               +
 *                /  \            /  \
 *               a    +          +    a
 *                   / \        / \
 *                  b   c      b   c
 *      输出：true
 *      解释：a + (b + c) == (b + c) + a
 *
 * 示例 3:
 *      输入： root1 = [+,a,+,null,null,b,c], root2 = [+,+,a,b,d]
 *                  +                   +
 *                /  \                /  \
 *               a    +              +    a
 *                   / \            / \
 *                  b   c          b   d
 *      输出： false
 *      解释： a + (b + c) != (b + d) + a
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示:</b>
 * <ul>
 *     <li>两棵树中的节点个数相等，且节点个数为范围 [1, 4999] 内的奇数。</li>
 *     <li>Node.val 是 '+' 或小写英文字母。</li>
 *     <li>给定的树保证是有效的二叉表达式树。</li>
 * </ul>
 * </p>
 * <b>进阶：当你的答案需同时支持 '-' 运算符（减法）时，你该如何修改你的答案</b>
 *
 * @author c2b
 * @since 2023/12/4 15:19
 */
public class LC1612CheckIfTwoExpressionTreesAreEquivalent_M {

    static class Solution {
        public boolean checkEquivalence(Node root1, Node root2) {
            int[] times = new int[26];
            dfs(root1, times,1);
            dfs(root2, times, -1);
            for (int time : times) {
                if (time != 0) {
                    return false;
                }
            }
            return true;
        }

        private void dfs(Node currNode, int[] times, int v) {
            if (currNode == null) {
                return;
            }
            if (currNode.val != '+') {
                times[currNode.val - 'a'] += v;
            }
            dfs(currNode.left, times, v);
            dfs(currNode.right, times, v);
        }

        /**
         * 进阶题解
         */
        public boolean checkEquivalence2(Node root1, Node root2) {
            int[] times1 = dfs(root1);
            int[] times2 = dfs(root2);
            for (int i = 0; i < 26; i++) {
                if (times1[i] != times2[i]) {
                    return false;
                }
            }
            return true;
        }

        private int[] dfs(Node currNode) {
            int[] times = new int[26];
            if (currNode == null) {
                return times;
            }
            if (currNode.val == '+' || currNode.val == '-') {
                // 左数字中每个字符出现的频次
                int[] lTimes = dfs(currNode.left);
                // 右树中每个字符出现的频次
                int[] rTimes = dfs(currNode.right);
                // 如果是'+'，左树中每个字符出现的频次 + 右树中每个字符出现的频次
                // 如果是'-'，左树中每个字符出现的频次 - 右树中每个字符出现的频次
                int k = currNode.val == '+' ? 1 : -1;
                for (int i = 0; i < 26; i++) {
                    times[i] = lTimes[i] + rTimes[i] * k;
                }
            } else {
                times[currNode.val - 'a']++;
            }
            return times;
        }
    }

    static class Node {
        char val;
        Node left;
        Node right;

        Node() {
            this.val = ' ';
        }

        Node(char val) {
            this.val = val;
        }

        Node(char val, Node left, Node right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
